package lc_1334_阈值距离内邻居最少的城市;

import java.util.Arrays;

public class SolutionFloyd {

	public int findTheCity(int n, int[][] edges, int distanceThreshold) {

		int[][] nexts = new int[n][n];

		for (int i = 0; i < n; i++) {
			Arrays.fill(nexts[i], Integer.MAX_VALUE / 2);
		}

		for (int[] e : edges) {
			int a = e[0], b = e[1], d = e[2];
			nexts[a][b] = nexts[b][a] = d;
		}

		for (int k = 0; k < n; k++) {
			nexts[k][k] = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					nexts[i][j] = Math.min(nexts[i][j], nexts[i][k] + nexts[k][j]);
				}
			}
		}
		int ans = -1, sum = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			int cnt = 0;
			for (int j = 0; j < n; j++) {
				if (nexts[i][j] <= distanceThreshold) {
					cnt++;
				}
			}
			if (cnt <= sum) {
				sum = cnt;
				ans = i;
			}
		}
		return ans;

	}

	public static void main(String[] args) {
		SolutionFloyd s = new SolutionFloyd();
		s.findTheCity(4, new int[][] { { 0, 1, 3 }, { 1, 2, 1 }, { 1, 3, 4 }, { 2, 3, 1 } }, 4);
	}
}